package com.liyunhan.SortAlgorithm;

import java.util.ArrayList;

/**
 * @Description: 快速排序非递归实现 (指定的low and high)
 * @Author: Liyunhan
 * @Date: 2021/10/4 17:10
 */
public class QuickSortNonRecursion extends AlgorithmAbs {

    public QuickSortNonRecursion(ArrayList<Double> arrayList) {
        super(arrayList);
    }

    @Override
    public void executeAlgorithm(int... ints) {
        //可变形参要求只能没有或者两个值
        if (ints.length != 2) {
            System.out.println("输入参数只能是0个或者两个!");
            System.exit(0);
        }
        //使用栈模拟
        int[] stack = new int[arrayList.size() / 2];
        int top = -1;
        int i = ints[0], j = ints[1];

        //先进行一次快速排序
        int index = onceQuickSort(i, j, arrayList);
        //判断当前index(上一轮快排枢轴)左右两侧是否有两个以上数据
        if (index > i + 1) {
            //index左侧序列两端元素入栈
            stack[++top] = i;
            stack[++top] = index - 1;
        }
        if (index < j - 1) {
            //index右侧序列两端元素入栈
            stack[++top] = index + 1;
            stack[++top] = j;
        }

        //此时左右序列部分端点元素均以入栈, 此时要判断当栈不空的时候
        //取出两个端点数对这段数据进行一次快排
        while (top > -1) {
            //注意此处取出要反着取
            j = stack[top--];
            i = stack[top--];
            index = onceQuickSort(i, j, arrayList);
            //判断当前index(上一轮快排枢轴)左右两侧是否有两个以上数据
            if (index > i + 1) {
                //index左侧序列两端元素入栈
                stack[++top] = i;
                stack[++top] = index - 1;
            }
            if (index < j - 1) {
                //index右侧序列两端元素入栈
                stack[++top] = index + 1;
                stack[++top] = j;
            }
        }
    }

    /**
     * 一次快速排序操作定义 (通用函数)
     *
     * @param i
     * @param j
     * @return
     */
    public static int onceQuickSort(int i, int j, ArrayList<Double> arrayList) {
        double pivot = arrayList.get(i);
        //一趟快速排序, 实现数组中小于枢轴(pivot)的关键字放左边, 大于枢轴的关键字放右边
        while (i < j) {
            //选择了左侧第一个为枢轴就要从右开始扫描, 找出一个小于pivot的关键字
            while (i < j && arrayList.get(j) >= pivot) {
                j--;
            }
            //每次都要判断是不是满足i<j, 否则ij已相遇, 本趟快排已经结束
            if (i < j) {
                arrayList.set(i, arrayList.get(j));
                //左指针向右移动
                i++;
            }

            //此时轮到左指针从左开始扫描
            while (i < j && arrayList.get(i) < pivot) {
                i++;
            }
            //每次都要判断是不是满足i<j, 否则ij已相遇, 本趟快排已经结束
            if (i < j) {
                arrayList.set(j, arrayList.get(i));
                //右指针向左移动
                j--;
            }
        }
        //将枢轴(pivot)放到最终位置
        arrayList.set(i, pivot);
        return i;
    }
}
